#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/raw_ostream.h"
#include <iostream>
//find from the list
#define FOUND(list, elem) \
    std::find(list.begin(), list.end(), elem) == list.end()

using namespace llvm;

namespace {

class LoopInvariantCodeMotion final : public LoopPass
{
private:
	DominatorTree * dom_tree;  // owned by `DominatorTreeWrapperPass`
    std::list<Instruction*> markedAsInvariant;
    
    // return true means is constant
    bool isInvariant(Instruction * I, Loop* loop)
    {
        bool is_invariant = true;//while be modified in the loop
        for(auto iter = I->op_begin(); is_invariant && iter != I->op_end(); ++iter)
        {
            Value* val = dyn_cast<Value>(*iter);
            assert(val != NULL);//if there is no Operator value
            if(!isa<Constant> (val)/*it is not constant*/ && !isa<Argument>(val)/*it hasn't been used as arguement*/)
            {
                if(Instruction* inst = dyn_cast<Instruction>(val))//The instruction used the value
                {
                   
                    if(FOUND(markedAsInvariant, inst)//if the instruction is not in the list,which means it is not an Invariant instruction
                        && loop->contains(inst->getParent()))
                        // not invariant
                        is_invariant = false;
                }
                else 
                {
                    // if it is not and instruction maybe a basic block
                    is_invariant = false;
                }
            }
        }
        return isSafeToSpeculativelyExecute(I)  // check undefined error
                                                
        && !I->mayReadFromMemory()              // if the instruction modifie Memory
        && !isa < LandingPadInst > (I)          // Exception deal related
        && is_invariant;                        
    }
    
    // check if the block inst belonged to dominate all blocks in the loop
    bool isDomExitblocks(Instruction* inst, Loop* loop)
    {
        SmallVector<BasicBlock*, 0> exitblock;
        loop->getExitBlocks(exitblock);//get all the blocks exit loop
        for(BasicBlock* bb : exitblock)
            // if there is an basicblock which is not dominated by inst
            if(!dom_tree->dominates(inst->getParent(), bb))
                return false;
        return true;
    }
    // if there is another instuction giving value to x
    bool AssignOnce(Instruction* inst)
    {
        // SSA
        return true;
    }
    // refrence to x is only available through inst
    bool OneWayToReferences(Instruction* inst)
    {
        // SSA
        return true;
    }    
    // move the instruction
    bool moveToPreheader(Instruction* inst, Loop* loop)
    {
        BasicBlock* preheader = loop->getLoopPreheader();
        // it's predominator shouldn't be void
        assert(preheader != NULL);
        /*  
            注意函数使用的是move，该函数会自动断开与原来基础块的连接，并移动到新的指令后面
            注意是移动到preheader的终结指令 *之前* 而不是 *之后* ，原因是
                1. 循环前置首节点最后一条指令是终结指令，移动到终结指令之后则肯定无法执行
                2. 最关键的一点，会报错，提示没有terminator
            基本块的终结指令基本上就是跳转指令
            同时，在这种情况下，不存在说，把指令移出来了，而该指令的操作数还在循环内部定值
        */
        inst->moveBefore(preheader->getTerminator());
        std::cout<<"Instruction has been moved\n";
        return false;
    }
public:
        static char ID;

	LoopInvariantCodeMotion() : LoopPass(ID) {}
	virtual ~LoopInvariantCodeMotion() override {}

    virtual void getAnalysisUsage(AnalysisUsage & AU) const
	{
		AU.addRequired < DominatorTreeWrapperPass > ();
        AU.addRequired < LoopInfoWrapperPass > ();
		AU.setPreservesCFG();
	}

    virtual bool runOnLoop(Loop * L, LPPassManager & LPM)
	{
        // if there is no pre-dominator basic block
        if(!L->getLoopPreheader())
            return false;
        std::cout<<L->getName()<<std::endl;
		dom_tree = &(getAnalysis < DominatorTreeWrapperPass > ().getDomTree());
        // clear the list
        markedAsInvariant.clear();
        // return value of runonloop
        bool IR_has_Changed = false;
        // add the code in the set
        bool hasChanged;
        do{
            hasChanged = false;
            for(BasicBlock* bb : L->blocks()){
                // loopinfo is the infomation of the current loop
                LoopInfo* loopinfo = &(getAnalysis < LoopInfoWrapperPass > ().getLoopInfo());
                
                if(loopinfo->getLoopFor(bb) == L){
                    for(Instruction& inst : *bb){
                        if(FOUND(markedAsInvariant, &inst)
                            && isInvariant(&inst, L)){
                            hasChanged = true;
                            markedAsInvariant.push_back(&inst);
                        }
                    } 
                }
            }
        }while(hasChanged);
        int moveCount = 0;
        for(Instruction* inst : markedAsInvariant)
        {
            
            if(isDomExitblocks(inst, L) && AssignOnce(inst) && OneWayToReferences (inst))
            {
                // move the instruction
                moveToPreheader(inst, L);
                IR_has_Changed = true;
                moveCount++;
            }
        }
        return IR_has_Changed;
    }
};

char LoopInvariantCodeMotion::ID = 0;

RegisterPass < LoopInvariantCodeMotion > X (
	"loop-invariant-code-motion",
	"Loop Invariant Code Motion");

}  // namespace anonymous